package Solution.problem091.DecodeWays;

/**
 * @program Leetcode
 * @description:
 * A message containing letters from A-Z is being encoded to numbers using the following mapping:
 *
 * 'A' -> 1
 * 'B' -> 2
 * ...
 * 'Z' -> 26
 * Given an encoded message containing digits, determine the total number of ways to decode it.
 *
 * For example,
 * Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
 *
 * The number of ways decoding "12" is 2.
 *https://www.cnblogs.com/271934Liao/p/6917298.html
 * 本题给出A-Z字符对应的数字，给出一个数字组成的字符串，要求求出可能A-Z组成的编码。
 * 这个题目还是一道动态规划题目：
 * 对于字符串中第i(i>2)个字符，因为编码最大的数字是26，
 * 所以到该点可能的编码方式和前一个字符也相关，如果当前字符和前一个字符组成的数字d=s.chaAt(i-1)*10+s.charAt(i)
 * (1) 当0<d=26,
 *      如果d%10!=0,有两种方式到达第i个字符，即f(s.charAt(i))=f(s.charAt(i-1))+f(s.charAt(i-2))；
 *      如果d%10=0,则只有一种方式达到f(s.charAt(i))=f(s.charAt(i-2))  这个就是个位为0
 *
 * （2）当d>26,
 *      如果d%10!=0,则一种方法到达i点（即从i-1到达i），f(s.charAt(i))=f(s.charAt(i-1))；
 *      如果d%10=0,则没有对应的编码表达d这两个字符，所以直接return 0
 *
 * （3）d==0的时候，字符串中出现了两个连续的0，直接return 0
 *
 *
 * @author: lishangsheng
 * @create: 2019/07/01 11:32
 */
public class Solution {
    public int numDecodings(String s) {

        int[] A=new int[s.length()];    //记录当前字符串第i个位置 的decode方法
        if(s.length()<=1){
            if(s.length()==0)
                return 0;
            else{
                if(s.charAt(0)=='0')
                    return 0;
                else
                    return 1;
            }
        }

        if(s.charAt(0)=='0')        //若包含0则返回0
            return 0;

        A[0]=1; //字符串第一位的数肯定只有一种匹配方法

        int x=(s.charAt(0)-'0')*10+(s.charAt(1)-'0');       //前两位数的值
        if(x>26&&x%10==0)
            /*比如30，没有办法完全解析*/
            return 0;
        if(x<=26&&x>0)
            if(x!=10&&x!=20)
                A[1]=2;
            else {
                A[1]=1;
            }
        else if(s.charAt(1)!='0')
            A[1]=1;
        else {
            A[1]=0;
        }

        for(int i=2;i<s.length();i++){
            //记录当前字符和前一个字符组成的数，若这个数小于等于26，则到当前的方法d(s.charAt(i))=d(s.charAt(i-1))+d(s.charAt(i-2)),否则d(s.charAt(i))=0
            int temp=(s.charAt(i-1)-'0')*10+(s.charAt(i)-'0');
            if(temp<=26&&temp>0)  //在0到26之间且前一个数不为0
                if(s.charAt(i-1)!='0'&&s.charAt(i)!='0')
                    A[i]=A[i-2]+A[i-1];
                else A[i]=A[i-2];
            else if(temp>26)     //中间有大于30的
                if(temp%10!=0)
                    A[i]=A[i-1];
                else {
                    return 0;
                }
            else        //包含两个连续的0
                return 0;
        }
        return A[s.length()-1];

    }
}
